package srcInterviewPrep;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;

public final class KnapSack
{
    public static int GetKnapSack(Item[] items, int w, List<Item> selectedItems)
    {
        // null check for items
        // W should be positive
        
        int n = items.length;
        
        int[][] M = new int[n+1][w+1];
        boolean[][] S = new boolean[n+1][w+1];
        
        for (int i = 0; i <= n; ++i)
        {
            M[i][0] = 0;
            S[i][0] = false;
        }
        
        for (int i = 0; i <= w; ++i)
        {
            M[0][i] = 0;
            S[0][i] = false;
        }
        
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= w; ++j)
            {
                if (j >= items[i-1].Weight)
                {
                    if (items[i-1].Value + M[i-1][j - items[i-1].Weight] > M[i-1][j])
                    {
                        S[i][j] = true;
                    }
                    else
                    {
                        S[i][j] = false;
                    }
                    
                    M[i][j] = Math.max(M[i-1][j], items[i-1].Value + M[i-1][j - items[i-1].Weight]);
                }
                else
                {
                    S[i][j] = false;
                    M[i][j] = M[i-1][j];
                }
            }
        }
        
        // FillSelectedItems(M, items, n, w, selectedItems);
        FillSelectedItemsIterative(S, items, n, w, selectedItems);
        return M[n][w];
    }
    
    private static void FillSelectedItems(int[][] M, Item[] items, int n, int w, List<Item> selectedItems)
    {
        if (n == 0 || w == 0)
        {
            return;
        }
        
        if (w < items[n-1].Weight)
        {
            FillSelectedItems(M, items, n-1, w, selectedItems);
        }
        else
        {
            boolean selected = (M[n-1][w - items[n-1].Weight] + items[n-1].Value > M[n-1][w]) ?  true : false;
            
            if (selected)
            {
                selectedItems.add(items[n-1]);
                FillSelectedItems(M, items, n-1, w - items[n-1].Weight, selectedItems);
            }
            else
            {
                FillSelectedItems(M, items, n-1, w, selectedItems);
            }
        }
    }
    
    private static void FillSelectedItemsIterative(
        boolean[][] S,
        Item[] items,
        int n,
        int w,
        List<Item> selectedItems)
    {
        while (n > 0)
        {
            Item item = items[n-1];
            --n;
            
            if (S[n][w])
            {
                selectedItems.add(item);
                w -= item.Weight;
            }
        }
    }   
}
